Interpolation

Numerical Analysis

Urbain Vaes

NYU Paris

Existence and uniqueness

Theorem (Existence and uniqueness)

Given data $x_0 < x_1< \dotsc < x_n$ and $y_0, \dotsc, y_n$, there exists a unique $p \in \mathcal P_n$ such that \[ \forall i \in \{0, \dotsc, n\}, \qquad p(x_i) = y_i. \]

Proof of existence: Define Lagrange polynomials \[ \forall i \in \{0, \dotsc, n\}, \qquad L_i(x) := \prod_{\substack{j = 0 \\ j \neq i}}^{n} \frac {x - x_j} {x_i - x_j}. \] Then set $p(x) = \sum_{i=0}^{n} y_i L_i(x)$ and verify that $p$ is an interpolating polynomial, which proves existence.

Proof of uniqueness: assume $q \in \mathcal P_n$ is another interpolating polynomial. Then $p - q \in \mathcal P_n$ and \[ \forall i \in \{0, \dotsc, n\}, \qquad p(x) - q(x) = 0. \] Thus $p - q$ is a polynomial of degree at most $n$ with $n + 1$ roots, so $p - q = 0$.

Illustration: Lagrange polynomials

Key property of Lagrange polynomials: \[ L_i(x_j) = \begin{cases} 1 & \text{if $i = j$} \\ 0 & \text{if $i \neq j$} \end{cases} \]

using Plots
using LaTeXStrings

# Interpolation nodes
x = [1, 2, 3]

function L(i, z)
    result = 1.0
    for j in 1:length(x)
        if i != j
            result *= (z - x[j]) / (x[i] - x[j])
        end
    end
    return result
end

scatter(x, ones(3), title="Lagrange polynomials")
plot!(legend=:outertopright, size=(900, 900))
plot!(z -> L(1, z), label=L"L_1")
plot!(z -> L(2, z), label=L"L_2")
plot!(z -> L(3, z), label=L"L_3")

Interpolation error

Theorem

Assumptions

$u\colon [a, b] \to \mathbf R$ is a $C^{n+1}([a, b])$ function
$a=x_0< x_1< \dotsc < x_n=b$ are $n+1$ distinct interpolation nodes
$\widehat u$ interpolates $u$ at $x_0, x_1, \dotsc, x_n$, i.e. $\widehat u(x_i) = u(x_i)$ for all $i ∈ \{0,\dotsc,n\}$

Then, it holds that $\quad ∀\, x ∈ [a,b],\quad ∃\, ξ=ξ(x) ∈ [a,b]$ \[ e_n(x) := u(x) - \widehat u(x) = \frac{u^{(n+1)}(\xi)}{(n+1)!} (x-x_0) \dotsc (x - x_n) \]

Corollary

Theorem

Assumptions

$u\colon [a, b] \to \mathbf R$ is a smooth function
$a=x_0< x_1< \dotsc < x_n=b$ are $n+1$ distinct interpolation nodes
$\widehat u$ interpolates $u$ at $x_0, x_1, \dotsc, x_n$.

Then it holds that \[ E_n := \sup_{x \in [a, b]} \bigl\lvert e_n(x) \bigr\rvert \leq \frac{C_{n+1}}{4(n+1)} h^{n+1}, \qquad C_{n+1} := \sup_{x \in [a, b]} \left\lvert u^{(n+1)}(x) \right\rvert. \] where $h$ is the maximum spacing between two successive interpolation nodes.

Chebyshev roots

Question? What nodes $(x_0, \dotsc x_n)$ to pick to minimize $(x-x_0) \dotsc (x - x_n)$? Recall \[ u(x) - \widehat u(x) = \frac{u^{(n+1)}(\xi)}{(n+1)!} (x-x_0) \dotsc (x - x_n) \]

Theorem

Assume that $p$ is a monic polynomial of degree $n \geq 1$: \[ p(x) = \alpha_0 + \alpha_1 x + \dotsb + \alpha_{n-1} x^{n-1} + x^n. \] Then it holds that \[ \label{eq:chebychev_lower_bound} \sup_{x \in [-1, 1]} \bigl\lvert p(x) \bigr\rvert \geq \frac{1}{2^{n-1}} =: E. \] In addition, the lower bound is achieved for $p_*(x) = 2^{-(n-1)} T_n(x)$, where $T_n$ is the Chebyshev polynomial of degree $n$: \[ \label{eq:chebyshev_polynomial} T_n(x) = \cos(n\arccos x) \qquad (-1 \leq x \leq 1). \]

$\leadsto$ Idea: use roots of $T_n$ as interpolation nodes

Sine function with equidistant nodes

\[ u(x)=\sin{x} \] \[ x_k=a + (b-a) \frac{k}{n} \quad (0 ≤ k ≤ n) \]

Runge function with equidistant nodes

\[ u(x)=\frac{1}{1+25x^2} \] \[ x_k=a + (b-a) \frac{k}{n} \quad (0 ≤ k ≤ n) \]

Optimization of the nodes: Chebyshev nodes

Idea: Take $x_0 < x_1 < \dotsc < x_n$ to be the roots of $T_n$:

\[ x_k=-\cos \Bigl(\pi \frac{k + \frac{1}{2}}{n} \Bigl), \qquad (0 ≤ k < n) \]